Search for: All records

We consider linear combinatorial optimization problems under uncertain disruptions that increase the cost coefficients of the objective function. A decision maker, or planner, can invest resources to probe the components (i.e., the coefficients) in order to learn their disruption status. In the proposed probing optimization problem, the planner, knowing just the disruptions’ probabilities, selects which components to probe subject to a probing budget in a first decision stage. Then, the uncertainty realizes, and the planner observes the disruption status of the probed components, after which the planner solves the combinatorial problem in the second stage. In contrast to standard two-stage stochastic optimization, the planner does not have access to the full uncertainty realization in the second stage. Consequently, the planner cannot directly optimize the second-stage objective function, which is given by the actual cost after disruptions, and the decisions have to be made based on an estimate of the cost. By assuming that the estimate is given by the conditional expected cost given the information revealed by probing, we reformulate the probing optimization problem as a bilevel problem with multiple followers and propose an exact algorithm based on a value function reformulation and three heuristic algorithms. We derive theoretical results that bound the value of information and the price of not having full information and a bound on the required probing budget that attains the same performance as full information. Our extensive computational experiments suggest that probing a fraction of the components is sufficient to yield large improvements in the optimal value, that our exact algorithm is competitive for small- to medium-scale instances, and that the proposed heuristics find high-quality solutions in large-scale instances. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. Funding: This work was supported by the Air Force Office of Scientific Research [Grant FA9550-22-1-0236] and the Division of Civil, Mechanical and Manufacturing Innovation [Grant CMMI 2145553]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2024.0629 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2024.0629 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ . 

We introduce the Influence Coverage Optimization Problem (ICOP), which is an influence maximization problem where the activation of nodes also depends on their location on the plane. Specifically, the ICOP assumes that there is a network where nodes become active (i.e., influenced) either by the influence they receive from interactions with active in-neighbors or by entering the coverage area of a physical ad or a Geo-fence. The objective is to locate a fixed number of ads or Geo-fences and modify the network influence rates to minimize the network activation time. Assuming a Markovian influence model, we prove that the ICOP is 𝑁𝑃-hard, and then we present mixed-integer programming formulations for three different types of coverage modes. A reformulation of the non-linear “big-M” constraints, two types of valid cuts, and a fast heuristic based on the k-means algorithm are used as enhancements that facilitate solving the ICOP via an Iterative Decomposition Branch-and-Cut (IDBC) algorithm. In addition, we present an alternative discrete formulation of the ICOP using critical intersection points. Several experiments under various parameter configurations across instances with more than a hundred nodes and thousand arcs are conducted, showing the IDBC’s capability to provide optimal solutions within seconds or minutes for most instances. Moreover, the experiments reveal that the ICOP can significantly outperform a Geo-fence coverage model that does not consider network interactions to make location decisions. 

Abstract The analysis of social and biological networks often involves modeling clusters of interest ascliquesor their graph‐theoretic generalizations. The ‐club model, which relaxes the requirement of pairwise adjacency in a clique to length‐bounded paths inside the cluster, has been used to model cohesive subgroups in social networks and functional modules or complexes in biological networks. However, if the graphs are time‐varying, or if they change under different conditions, we may be interested in clusters that preserve their property over time or under changes in conditions. To model such clusters that are conserved in a collection of graphs, we consider across‐graph‐clubmodel, a subset of nodes that forms a ‐club in every graph in the collection. In this article, we consider the canonical optimization problem of finding a cross‐graph ‐club of maximum cardinality in a graph collection. We develop integer programming approaches to solve this problem. Specifically, we introduce strengthened formulations, valid inequalities, and branch‐and‐cut algorithms based on delayed constraint generation. The results of our computational study indicate the significant benefits of using the approaches we introduce. 

We introduce a new variant of the network interdiction problem with a Markovian evader that randomly chooses a neighboring vertex in each step to build their path from designated source(s) to terminal(s). The interdictor's goal is to maximize the evader's minimum expected first passage time. We establish sufficient conditions for the interdiction to not be counter-productive, prove that the problem is NP-hard, and demonstrate the model's usefulness by solving a mixed-integer programming formulation on a test bed of social networks.